package org.example.l0;

import org.junit.jupiter.api.Test;

import java.util.Stack;

public class decodeString {
    @Test
    void aa() {
        //                String aa = "3[a]2[bc]";
//        String aa = "100[leetcode]";
        String aa = "2[20[bc]31[xy]]xd4[rt]";
        String ab = decodeString(aa);
        System.out.println(ab);
    }

    char LEFT = '[', RIGHT = ']';

    public String decodeString(String s) {
        int begin = s.indexOf(LEFT);
        if (begin == -1) {
            return s;
        }
        int numLen = findNumLen(s, begin);
        StringBuilder builder = new StringBuilder(s.substring(0, begin - numLen));

        int end = -1;
        while (begin != -1) {
            end = findEnd(s, begin);
            String base = decodeString(s.substring(begin + 1, end));
            int num = findNum(s, begin);
            while (num-- > 0) {
                builder.append(base);
            }

            begin = s.indexOf(LEFT, end);
            if (begin != -1) {
                int numLen1 = findNumLen(s, begin);
                String substring = s.substring(end + 1, begin - numLen1);
                builder.append(substring);
            }
        }

        if (end != -1 && end != s.length()) {
            builder.append(s.substring(end + 1));
        }

        return builder.toString();
    }

    int findEnd(String s,
                int begin) {
        Stack<Character> stack = new Stack<>();
        stack.push(LEFT);
        for (int i = begin + 1; i < s.length(); i++) {
            char charAt = s.charAt(i);
            if (charAt == LEFT) {
                stack.push(LEFT);
            }

            if (charAt == RIGHT) {
                stack.pop();
                if (stack.isEmpty()) {
                    return i;
                }
            }
        }
        return -1;
    }

    int findNumLen(String s,
                   int begin) {
        int num = findNum(s, begin);
        return (int) (Math.log10(num) + 1);
    }

    int findNum(String s,
                int begin) {
        int num = 0;
        for (int idx = begin - 1, multi = 1; idx >= 0; idx--, multi *= 10) {
            char charAt = s.charAt(idx);
            if (!Character.isDigit(charAt)) {
                return num;
            }

            int n = charAt - '0';
            num += n * multi;
        }

        return num;
    }
}
